Data communication systems are used to exchange information between devices. The information to be exchanged comprises data that is organized as strings of digital bits formatted so as to be recognizable by other devices and to permit the information to be processed and/or recovered.
The exchange of information may occur over a publically accessible network, such as a communication link between two devices, over a dedicated network within an organization, or may be between two devices within the same dedicated component, such as within a computer or point of sale device.
The devices may range from relatively large computer systems through to telecommunication devices, cellular phones, monitoring devices, sensors, electronic wallets and smart cards, and a wide variety of devices that are connected to transfer data between two or more of such devices.
A large number of communication protocols have been developed to allow the exchange of data between different devices. The communication protocols permit the exchange of data in a robust manner, often with error correction and error detection functionality, and for the data to be directed to the intended recipient and recovered for further use.
Because the data may be accessible to other devices, it is vulnerable to interception and observation or manipulation. The sensitive nature of the information requires that steps are taken to secure the information and ensure its integrity.
A number of techniques collectively referred to as encryption protocols and authentication protocols have been developed to provide the required attributes and ensure security and/or integrity in the exchange of information. These techniques utilize a key that is combined with the data.
There are two main types of cryptosystems that implement the protocols, symmetric key cryptosystems and asymmetric or public key cryptosystems. In a symmetric key cryptosystem, the devices exchanging information share a common key that is known only to the devices intended to share the information. Symmetric key systems have the advantage that they are relatively fast and therefore able to process large quantities of data in a relatively short time, even with limited computing power. However, the keys must be distributed in a secure manner to the different devices, which leads to increased overhead and vulnerability if the key is compromised.
Asymmetric or public key cryptosystems utilize a key pair, one of which is public and the other private, associated with each device. The public key and private key are related by a “hard” mathematical problem so that even if the public key and the underlying problem are known, the private key cannot be recovered in a feasible time. One such problem is the factoring of the product of two large primes, as utilized in RSA cryptosystems. Another is the discrete log problem in a finite group. A generator, α, of the underlying group is identified as a system parameter and a random integer, k, generated for use as a private key. To obtain a public key, K, a k-fold group operation is performed so that K=f(α,k).
Different groups may be used in discrete log cryptosystems including the multiplicative group of a finite field, the group of integers in a finite cyclic group of order p, usually denoted Zp* and consisting of the integers 0 to p−1. The group operation is multiplication so that K=f(αk).
Another group that is used for enhanced security is an elliptic curve group. The elliptic curve group consists of pairs of elements, one of which is designated x and the other y, in a field that satisfy the equation of the chosen elliptic curve. For an elliptic curve group of order p, the elliptic curve would generally be defined by the relationship y2 mod p=x3+ax+b mod p. Other curves are used for different groups, as is well known. Each such pair of elements is a point on the curve, and a generator of the group is designated as a point P. The group operation is addition, so a private key k will have a corresponding public key f(kP).
Public key cryptosystems reduce the infrastructure necessary with symmetric key cryptosystems. A device may generate an integer k, and generate the corresponding public key kP. The public key is published so it is available to other devices. The device may then use a suitable signature protocol to sign a message using the private key k and other devices can confirm the integrity of the message using the public key kP.
Similarly, a device may encrypt a message to be sent to another device using the other devices public key. The message can then be recovered by the other device using the private key. However, these protocols are computationally intensive, and therefore relatively slow, compared with symmetric cryptosystem protocols.
Public key cryptosystems may also be used to establish a key that is shared between two devices. In its simplest form, as proposed by Diffie-Hellman, each device sends a public key to the other device. Both devices then combine the received public key with their private key to obtain a shared key.
One device, usually referred to as an entity (or correspondent), Alice, generates a private key ka and sends another device, or entity, Bob, the public key kaP.
Bob generates a private key kb and sends Alice the public key kbP
Alice computes ka·kbP and Bob computes kb·kaP so they share a common key K=kakbp=kbkaP. The shared key may then be used in a symmetric key protocol. Neither Alice nor Bob may recover the private key of the other, and third parties cannot reconstruct the shared key.
In order to ensure integrity of the shared key, and to rebut attacks that have been developed to recover or substitute the shared key and/or the private keys within the shared key, key establishment protocols have been developed.
Key establishment is the process by which two (or more) entities establish a shared secret key. The key is subsequently used to achieve some cryptographic goal such as confidentiality or data integrity.
Broadly speaking, there are two kinds of key establishment protocols: key transport protocols in which a key is created by one entity and securely transmitted to the second entity, and key agreement protocols in which both parties contribute information which jointly establish the shared secret key. The present application is directed to key agreement protocols for the asymmetric (public-key) cryptosystems.
If Alice and Bob are two honest entities, i.e., legitimate entities who execute the steps of a protocol correctly, then informally speaking, a key agreement protocol is said to provide implicit key authentication (of Bob to Alice) if entity Alice is assured that no other entity aside from a specifically identified second entity Bob can possibly learn the value of a particular secret key. The property of implicit key authentication does not necessarily mean that Alice is assured of Bob actually possessing the key, but is assured that no one other than Bob possesses the key. A key agreement protocol which provides implicit key authentication to both participating entities is called an authenticated key agreement (AK)protocol.
Informally speaking, a key agreement protocol is said to provide key confirmation (of Bob to Alice) if entity A is assured that the second entity Bob actually has possession of a particular secret key. If both implicit key authentication and key confirmation (of Bob to Alice) are provided, then the key establishment protocol is said to provide explicit key authentication (of Bob to Alice). A key agreement protocol which provides explicit key authentication to both participating entities is called an authenticated key agreement with key confirmation (AKC) protocol. An extensive survey on key establishment is provided at Chapter 12 of Menezes, van Oorshot and Vanstone's Handbook of Applied Cryptography, the contents of which are incorporated by reference.
Extreme care must be exercised when separating key confirmation from implicit key authentication. If an AK protocol which does not offer key confirmation is used, then, as pointed out in the 1997 paper by S. Blake-Wilson, D. Johnson, and A. Menezes entitled “Key agreement protocols and their security analysis”, it is desirable that the agreed key be confirmed prior to cryptographic use. This can be done in a variety of ways. For example, if the key is to be subsequently used to achieve confidentiality, then encryption with the key can begin on some (carefully chosen) known data. Other systems may provide key confirmation during a “real-time” telephone conversation. Separating key confirmation from implicit key authentication is sometimes desirable because it permits flexibility in how a particular implementation chooses to achieve key confirmation, and thus moves the burden of key confirmation from the establishment mechanism to the application.
Numerous Diffie-Hellman-based AK and AKC protocols have been proposed over the years; however, many have subsequently been found to have security flaws. The main problems were that appropriate threat models and the goals of secure AK and AKC protocols lacked a formal definition. Blake-Wilson, Johnson and Menezes, adapting earlier work of Bellare and Rogaway in the symmetric setting, provided a formal model of distributed computing and rigorous definitions of the goals of secure AK and AKC protocols within this model. Concrete AK and AKC protocols were proposed, and proven secure within this framework in the random oracle model.
It is expected that a secure protocol should be able to withstand both passive attacks (where an adversary attempts to prevent a protocol from achieving its goals by merely observing honest entities carrying out the protocol) and active attacks (where an adversary additionally subverts the communications by injecting, deleting, altering or replaying messages).
In addition to implicit key authentication and key confirmation, a number of desirable security attributes of AK and AKC protocols have been identified:                1. known-key security. Each run of a key agreement protocol between A and B should produce a unique secret key; such keys are called session keys. A protocol should still achieve its goal in the face of an adversary who has learned some other session keys.        2. (perfect) forward secrecy. If long-term keys of one or more entities are compromised, the secrecy of previous session keys established by honest entities are not affected.        3. key-compromise impersonation. Suppose A′s long-term key is disclosed. Clearly an adversary that knows this value can now impersonate A, since it is precisely this value that identifies A. However, it may be desirable that this loss does not enable an adversary to impersonate other entities to A.        4. unknown key-share. Entity A cannot be coerced into sharing a key with entity B without A's knowledge, i.e. when A believes the key is shared with some entity C≠B, and B (correctly) believes the key is shared with A.        5. key control. Neither entity should be able to force the session key to a preselected value.        
Desirable performance attributes of AK and AKC protocols include a minimal number of passes (the number of messages exchanged in a run of the protocol), low communication overhead (total number of bits transmitted), and low computation overhead. Other attributes that may be desirable in some circumstances include role-symmetry (the messages transmitted between entities have the same structure), non-interactiveness (the messages transmitted between the two entities are independent of each other), and the non-reliance on encryption, hash functions (since these are notoriously hard to design), and timestamping (since it is difficult to implement securely in practice).
It is therefore an object of the present invention to provide a key agreement protocol in which the above disadvantages are obviated or mitigated and attainment of the desirable attributes is facilitated.